This invention relates to routing algorithms which support multiple protocols.
The end systems (e.g., computers or printers) which form a computer network are interconnected by devices known as routers. Each end system is attached to one of the network's routers and each router is responsible for forwarding communications to and from its attached end systems.
The routers transfer information to and from the end systems and among themselves along communications links in formatted packets. For example, when an originating end system wishes to transmit information to a destination end system, it generates a packet header in an appropriate format (this header includes, among other information, the address of the destination end system), and then fills the remainder of the packet with the information to be transmitted. (In the following description, the term "user data packet" will refer to the entire packet, i.e. the formatted header and the information that is to be transmitted from end system to end system.) The completed user data packet is then provided to the router attached to (and responsible for) the originating end system, which forwards it toward the destination end system. Packets transmitted among the routers themselves (which will be referred to as "control packets") are similarly formatted and forwarded.
When a router receives a user data packet, it reads the user data packet's destination address from the user data packet header, and then transmits the user data packet on the link leading most directly to the user data packet's destination. Along the path from source to destination, a user data packet may be transmitted along several links and pass through several routers, each router on the path reading the user data packet header and forwarding the user data packet accordingly.
To determine how user data packets should be forwarded, each router typically knows the locations of the network's end systems (i.e., which routers are responsible for which end systems), the nature of the connections between the routers, and the states (e.g., operative or inoperative) of the links forming those connections. Using this information, each router can compute effective routes through the network and avoid, for example, faulty links or routers. A procedure for performing these tasks is generally known as a "routing algorithm".
In popular routing algorithms such as that described in "The New Routing Algorithm for the ARPANET" by McQuillan et al., IEEE Transactions on Communications, May, 1980, each router determines which end systems are attached to it, what links to other routers are available, the states of those links, and the identities of the routers on the other ends of those links. To initialize the network, each router places this information in a control packet known as a Link State packet (LSP), and transmits this LSP to all of the other routers in the network (i.e., "advertises" its neighbors and end systems to the network). Later, when changes in the network occur (e.g., a link fails), one or more routers may generate new LSPs which supersede previously generated LSPs.
As long as the most recent LSPs are propagated reliably to all of the routers, each router will have complete information about the topology of the network and can generate a routing database describing routes through the network (for example, using the algorithm described in "A Note on Two Problems in Connexion with Graphs" by Edsgar Dijkstra, Numerische Mathematik, Vol. 1, 1959, pages 269-271).
In order for user data packets to be delivered to their destinations, each end system on the network must have an unambiguous address. There are several independent standards organizations which document and promulgate address allocation schemes, as well as control and user data packet formats which may be used for communicating under these schemes. Several networks of routers have been configured according to these addressing schemes and formats.
In what follows, the term "routing protocol" will be used to describe the combination of an address allocation scheme and a format (or a group of related formats) that describes control packets and other information to be exchanged among routers, and which is used to calculate the paths which the user data packets will take between routers. Routing protocols are often associated with their own routing algorithms, each routing algorithm being documented and promulgated by the standards organization responsible for the associated routing protocol.
Further, the term "protocol suite" will be used to describe the comprehensive set of protocols that is designed to work together to coherently provide complete communication capabilities. Two examples of protocol suites are the TCP/IP protocol suite and the OSI protocol suite. Each of these protocol suites includes one or more network layer protocols which define the format used for control and user data packets that are to be transferred by the network routers. For example, the IP protocol of the TCP/IP protocol suite defines the network layer protocol which makes up the format of the user data packets that are forwarded by the IP routers. Similarly, the OSI routers forward user data packets following the ISO 8473 network layer protocol.
The Transmission Control Protocol (TCP) RFC 793, Internetwork Protocol (IP) RFC 791, the Internet Control Message Protocol RFC 792, and the TCP/IP protocol suite which is described in RFC 1122, "Requirements for Internet Hosts--Communication Layers," RFC 1123, "Requirements for Internet Hosts Application and Support," RFC 1100, "IAB Official Protocol Standards," and RFC 1009, "Requirements for Internet Gateways," and associated other RFCs, all available from SRI International, DDN Network Information Center, Room EJ291, 333 Ravenswood Avenue, Menlo Park, Calif. 94025, have recently been growing in importance as a multi-vendor communications architecture, and many networks are based on them. (TCP/IP terminology refers to routers as "gateways", and end systems as "hosts".) At the same time, however, existing networks also use the Open Systems Interconnection (OSI) protocols such as described in International Organization for Standardization (ISO) 7498, "Information Processing Systems--Open Systems Interconnection--Basic Reference Model, " ISO 8473, "Protocol for Providing the Connectionless-mode Network Service," ISO 9542, "End System to Intermediate System Routing Exchange Protocol," and ISO DP 10589 "Intermediate System to Intermediate System Intradomain Routing Exchange Protocol," all available from BSi Standards, 2 Park Street, London England, W1A 2BS, and more are expected to be created as OSI is further developed.
Because the several existing protocols (in particular TCP/IP and OSI) have been developed independently, they are largely incompatible.
Networks having incompatible protocols cannot make their links and routers available to each other, which may result in excess redundancy and reduced efficiency. Also, each of the networks must be maintained independently, increasing the total management effort over what would be required by a single, universally compatible network.
One known way to share routing resources among networks having incompatible protocols is known as gateway encapsulation. In gateway encapsulation, a network using protocol A is provided with a path through a second network that uses protocol B. To form the path, two routers are manually configured to provide gateways from protocol A to protocol B, and back.
Each gateway router is configured to be fluent in both protocol A and protocol B. When a user data packet formatted in protocol A is received at a gateway router, the gateway router "encapsulates" the user data packet in a protocol B header (i.e., generates a protocol B header and places the protocol A user data packet, including the protocol A header, into the data area of the protocol B user data packet). The encapsulated protocol A user data packet is then addressed to the second gateway router, and transmitted through the protocol B network.
When the encapsulated protocol A user data packet is received at the second gateway router, the protocol B encapsulation header is removed, and the protocol A user data packet is forwarded to its destination through the protocol A network.
The routing algorithm used in the protocol A network is suitably modified to make the protocol A routers aware of the gateway, so that user data packets destined to routers at the other end of the gateway are forwarded to one of the gateway routers.
One disadvantage of gateway encapsulation is that the gateway must be manually configured, and thus must also be manually maintained. If a change to the gateway path is desired, or if an additional gateway path is added, the gateway routers must be manually adjusted to effect the desired changes. Furthermore, the gateway path is only available to the protocol A network as long as the gateway routers themselves are operational. If a gateway router fails, the pre-established path through the protocol B network is severed, and communications must be re-routed through the protocol A network.
Another way to route multiple incompatible protocols is known as "ships in the night" (SIN). In the SIN approach, the same physical resources (e.g., routers and links) are used to route completely separate protocols. The shared resources multiplex between the supported protocols, and the protocols themselves operate more or less independently.
With SIN, there is some degree of competition for resources, because implementing two protocols requires additional programming time as well as additional CPU and memory resources in the routers. Furthermore, SIN requires that two complete sets of control packets be distributed through the two independent networks, which doubles the control traffic overhead over that of a single integrated network. Finally, configuring and managing multiple independent networks is less efficient than configuring and managing a single integrated network of the same total size: multiple networks must be configured independently, increasing overhead; and multiple networks cannot be managed as efficiently as a single network because the implicit interactions between the networks (such as the shared loads placed on routers and links) cannot be well characterized and controlled.